package com.mc.sort;

import java.util.Arrays;
import java.util.HashSet;

/**
 * @Description: 插入排序
 * @Author: MoChen
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arrs = {1, 2, 5, 3, 6, 7, 4};
        InsertSort is = new InsertSort();
        System.out.println(Arrays.toString(is.bInsSort(arrs)));
    }

    /**
     * 每次将当前数字与前面所有位数比较，前面大则交换，否则看下一个数字
     */
    public int[] insSort(int[] arrs){
        for (int i = 1; i < arrs.length; i++) {
            int j = i;
            while (j > 0){
                if (arrs[j] < arrs[j - 1]){
                    int temp ;
                    temp = arrs[j];
                    arrs[j] = arrs[j - 1];
                    arrs[j-1] = temp;
                    j--;
                }else {
                    break;
                }
            }
        }
        return arrs;
    }

    /**
     * 1. 从第二个数字开始遍历，将当前数字放入数组第一位当作哨兵使用
     * 2. 从当前数字往前遍历，只要大于哨兵就往前移一位
     * 3. 将哨兵赋给下一位，完成交换操作
     * 4. 重复以上操作，直到数据完成排序
     */
    public int[] insSortSent(int[] arrs){
        int i = 0, j = 0;
        int[] newArrs = new int[arrs.length + 1];
        // 将当前数组扩容一位，保证第一位是哨兵
        System.arraycopy(arrs, 0, newArrs, 1, arrs.length);
        for(i = 2; i < newArrs.length; i++){
            newArrs[0] = newArrs[i];
            for(j = i - 1; newArrs[0] < newArrs[j]; j--){
                newArrs[j + 1] = newArrs[j];
            }
            newArrs[j + 1] = newArrs[0];
        }
        // 归还结果
        arrs = Arrays.copyOfRange(newArrs, 1, newArrs.length);
        return arrs;
    }

    /**
     * 折半插入排序
     */
    public int[] bInsSort(int[] arrs){
        int i = 0,j = 0;
        int low = 0, high = 0, mid = 0;
        int[] newArrs = new int[arrs.length + 1];
        // 将当前数组扩容一位，保证第一位是哨兵
        System.arraycopy(arrs, 0, newArrs, 1, arrs.length);
        for(i = 2; i < newArrs.length; i++){
            newArrs[0] = newArrs[i];
            low = 1;
            high = i - 1;
            while(low <= high){
                mid = (low + high) / 2;
                if(newArrs[mid] > newArrs[0]){
                    high = mid - 1;
                }else{
                    low = mid + 1;
                }
            }
            for(j = i - 1; j >= high + 1; j--){
                newArrs[j + 1] = newArrs[j];
            }
            newArrs[high + 1] = newArrs[0];
        }
        // 归还结果
        arrs = Arrays.copyOfRange(newArrs, 1, newArrs.length);
        return arrs;
    }
}
